/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 王洋
 * Date: 2025-09-06
 * Time: 17:10
 */
class Solution {
    //75. 颜色分类
    /*给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，
    原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
    我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
    必须在不使用库内置的 sort 函数的情况下解决这个问题。
    示例 1：
    输入：nums = [2,0,2,1,1,0]
    输出：[0,0,1,1,2,2]
    示例 2：
    输入：nums = [2,0,1]
    输出：[0,1,2]
    提示：
    n == nums.length
1 <= n <= 300
    nums[i] 为 0、1 或 2
    进阶：
    你能想出一个仅使用常数空间的一趟扫描算法吗？*/
    public void swap(int[] nums,int i,int j){
        int t=nums[i];
        nums[i]=nums[j];
        nums[j]=t;
    }
    public void sortColors(int[] nums) {
        //如果用三个if会导致在同一个循环内多次进行判断和交换
        int left=-1,i=0,right=nums.length;
        while(i<right){
            if(nums[i]==0) swap(nums,++left,i++);
                //左侧是i扫描过的，所以i++
            else if(nums[i]==1) i++;
            else swap(nums,--right,i);
            //右边是i没扫描到的,所以i不++
        }
    }
}
